package main

import "fmt"

/*
给你一个整数数组 nums，请你将该数组升序排列。
*/
func main() {
	nums := []int{5, 1, 1, 2, 0, 0}
	sortArray(nums)
	for _, v := range nums {
		fmt.Printf("%d ", v)
	}
}
func sortArray(nums []int) (arr []int) {
	quickSort(nums, 0, len(nums)-1)
	return nums
}

/**
 *	quickSort
 *	@Description: 快速排序
 *	@param nums []int
 *	@param left int
 *	@param right int
 */
func quickSort(nums []int, left, right int) {
	if left >= right {
		return
	}
	i, j := left-1, right+1
	mid := nums[(left+right)>>1]
	for i < j {
		for {
			i++
			if nums[i] >= mid {
				break
			}
		}
		for {
			j--
			if nums[j] <= mid {
				break
			}
		}
		if i < j {
			nums[i], nums[j] = nums[j], nums[i]
		}
	}
	quickSort(nums, left, j)
	quickSort(nums, j+1, right)
}
